home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C++ / Libraries / KPlib 1.2.1 / KPPriorityQueue.h < prev    next >
Encoding:
Text File  |  1994-11-07  |  5.9 KB  |  233 lines  |  [TEXT/R*ch]
  1. // A module of KPlib v1.2.1.
  2. // Written by Keith Pomakis during the summer of 1994.
  3. // Released to the public domain on October 10, 1994.
  4.  
  5. #ifndef KP_PRIORITY_QUEUE_DEFINED
  6. #define KP_PRIORITY_QUEUE_DEFINED
  7.  
  8. #include <stdlib.h>
  9. #include "KPbasic.h"
  10. #include "KPList.h"
  11.  
  12. // Assumes Element has a default constructor, operator=(), operator==(),
  13. // and operator<().  Note that operator<() must place a total ordering on
  14. // the set of Elements.
  15.  
  16. template <class Element>
  17. class KPPriorityQueue {
  18.     public:
  19.         KPPriorityQueue();
  20.         KPPriorityQueue(const KPPriorityQueue &queue);
  21.         KPPriorityQueue(const KPList<Element> &list);
  22.         KPPriorityQueue(const Element &element);
  23.         ~KPPriorityQueue();
  24.         operator KPList<Element>() const;
  25.         KPPriorityQueue &operator=(const KPPriorityQueue &queue);
  26.         KPPriorityQueue &operator=(const Element &element);
  27.         KPPriorityQueue &enqueue(const Element &element);
  28.         Element dequeue();
  29.         Element &head();
  30.         const Element &head() const;
  31.         Element &tail();
  32.         const Element &tail() const;
  33.         int size() const;
  34.         bool is_empty() const;
  35.         KPPriorityQueue &clear();
  36.     protected:
  37.         static void queue_empty_error(const char *fname);
  38.         KPSortableList<Element> my_list;
  39. };
  40.  
  41. /****************************************************************************/
  42.  
  43. template <class Element>
  44. inline
  45. KPPriorityQueue<Element>::KPPriorityQueue(): my_list()
  46. { /* do nothing. */ }
  47.  
  48. /****************************************************************************/
  49.  
  50. template <class Element>
  51. inline
  52. KPPriorityQueue<Element>::KPPriorityQueue(const KPPriorityQueue<Element>
  53.                                             &queue): my_list(queue.my_list)
  54. { /* do nothing. */ }
  55.  
  56. /****************************************************************************/
  57.  
  58. template <class Element>
  59. inline
  60. KPPriorityQueue<Element>::KPPriorityQueue(const KPList<Element> &list):
  61.                                                                 my_list(list)
  62. {
  63.     my_list.sort();
  64. }
  65.  
  66. /****************************************************************************/
  67.  
  68. template <class Element>
  69. inline
  70. KPPriorityQueue<Element>::KPPriorityQueue(const Element &element):
  71.                                                             my_list(element)
  72. { /* do nothing. */ }
  73.  
  74. /****************************************************************************/
  75.  
  76. template <class Element>
  77. inline
  78. KPPriorityQueue<Element>::~KPPriorityQueue()
  79. {
  80.     my_list.clear();
  81. }
  82.  
  83. /****************************************************************************/
  84.  
  85. template <class Element>
  86. inline
  87. KPPriorityQueue<Element>::operator KPList<Element>() const
  88. {
  89.     return my_list;
  90. }
  91.  
  92. /****************************************************************************/
  93.  
  94. template <class Element>
  95. inline KPPriorityQueue<Element> &
  96. KPPriorityQueue<Element>::operator=(const KPPriorityQueue<Element> &queue)
  97. {
  98.     my_list = queue.my_list;
  99.     return *this;
  100. }
  101.  
  102. /****************************************************************************/
  103.  
  104. template <class Element>
  105. inline KPPriorityQueue<Element> &
  106. KPPriorityQueue<Element>::operator=(const Element &element)
  107. {
  108.     my_list = element;
  109.     return *this;
  110. }
  111.  
  112. /****************************************************************************/
  113.  
  114. template <class Element>
  115. KPPriorityQueue<Element> &
  116. KPPriorityQueue<Element>::enqueue(const Element &element)
  117. {
  118.     KPIterator<Element> iter(my_list);
  119.  
  120.     iter.end();
  121.     while (iter.ptr() && element < *iter)
  122.         iter--;
  123.     if (!iter.ptr())
  124.         my_list.add_to_head(element);
  125.     else
  126.         iter.insert_after_current(element);
  127.  
  128.     return *this;
  129. }
  130.  
  131. /****************************************************************************/
  132.  
  133. template <class Element>
  134. inline Element
  135. KPPriorityQueue<Element>::dequeue()
  136. {
  137.     if (my_list.size() < 1)
  138.         queue_empty_error("dequeue()");
  139.     
  140.     Element element = my_list.head();
  141.     my_list.remove_head();
  142.     return element;
  143. }
  144.  
  145. /****************************************************************************/
  146.  
  147. template <class Element>
  148. inline Element &
  149. KPPriorityQueue<Element>::head()
  150. {
  151.     if (my_list.size() < 1)
  152.         queue_empty_error("head()");
  153.  
  154.     return my_list.head();
  155. }
  156.  
  157. /****************************************************************************/
  158.  
  159. template <class Element>
  160. inline const Element &
  161. KPPriorityQueue<Element>::head() const
  162. {
  163.     if (my_list.size() < 1)
  164.         queue_empty_error("head()");
  165.  
  166.     return my_list.head();
  167. }
  168.  
  169. /****************************************************************************/
  170.  
  171. template <class Element>
  172. inline Element &
  173. KPPriorityQueue<Element>::tail()
  174. {
  175.     if (my_list.size() < 1)
  176.         queue_empty_error("tail()");
  177.  
  178.     return my_list.tail();
  179. }
  180.  
  181. /****************************************************************************/
  182.  
  183. template <class Element>
  184. inline const Element &
  185. KPPriorityQueue<Element>::tail() const
  186. {
  187.     if (my_list.size() < 1)
  188.         queue_empty_error("tail()");
  189.  
  190.     return my_list.tail();
  191. }
  192.  
  193. /****************************************************************************/
  194.  
  195. template <class Element>
  196. inline int
  197. KPPriorityQueue<Element>::size() const
  198. {
  199.     return my_list.size();
  200. }
  201.  
  202. /****************************************************************************/
  203.  
  204. template <class Element>
  205. inline bool
  206. KPPriorityQueue<Element>::is_empty() const
  207. {
  208.     return my_list.is_empty();
  209. }
  210.  
  211. /****************************************************************************/
  212.  
  213. template <class Element>
  214. inline KPPriorityQueue<Element> &
  215. KPPriorityQueue<Element>::clear()
  216. {
  217.     my_list.clear();
  218. }
  219.  
  220. /****************************************************************************/
  221.  
  222. template <class Element>
  223. void
  224. KPPriorityQueue<Element>::queue_empty_error(const char *fname)
  225. {
  226.     cerr << "KPPriorityQueue: " << fname << " - queue empty\n";
  227.     exit(EXIT_FAILURE);
  228. }
  229.  
  230. /****************************************************************************/
  231.  
  232. #endif /* KP_PRIORITY_QUEUE_DEFINED */
  233.